// 带头结点的链队列
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ERROR -999

typedef int ElementType;
struct Node
{
    ElementType Data;
    struct Node* Next;
};
typedef struct Node* PtrToNode;
struct QNode
{
    PtrToNode Front;
    PtrToNode Rear;
};
typedef struct QNode* PtrToQNode;
typedef PtrToQNode Queue;

Queue CreateQueue()
{
    Queue Q = (Queue) malloc(sizeof(struct QNode));
    Q->Front = Q->Rear = (PtrToNode) malloc(sizeof(struct Node));
    Q->Front->Next = NULL;
    return Q;
}

bool IsEmpty(Queue Q)
{
    return Q->Front->Next == NULL;
}

bool Enqueue(Queue Q, ElementType X)
{
    PtrToNode TmpCell = (PtrToNode) malloc(sizeof(struct Node));
    TmpCell->Data = X;
    TmpCell->Next = NULL;
    Q->Rear->Next = TmpCell;
    Q->Rear = TmpCell;
    return true;
}

ElementType Dequeue(Queue Q)
{
    if (IsEmpty(Q)) {
        printf("队列已空，不能出队\n");
        return ERROR;
    }
       
    PtrToNode p = Q->Front->Next;
    ElementType result = p->Data;
    Q->Front->Next = p->Next;
    if (Q->Rear == p) {
        Q->Rear = Q->Front;
    }
    free(p);
    return result;
}

void Print_Queue(Queue Q)
{
    PtrToNode p = Q->Front;
    while (p ->Next!= NULL) {
        p = p->Next;
        printf("%d ", p->Data);
        
    }
}

int main()
{
    Queue Q = CreateQueue();
    Enqueue(Q, 1);
    Enqueue(Q, 2);
    Enqueue(Q, 3);
    Enqueue(Q, 4);
    Dequeue(Q);
    Dequeue(Q);
    Dequeue(Q);
    Dequeue(Q);
    Dequeue(Q);
    // ElementType x = Dequeue(Q);
    // printf("x = %d\n", x);
    // x = Dequeue(Q);
    // printf("x = %d\n", x);
    Print_Queue(Q);
}